package com.sloan.community.util.test;

import java.util.ArrayList;
import java.util.List;

public class MergeIntervals {

    // Index类定义
    public static class Index {
        public int left;
        public int right;

        public Index(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Index{left=" + left + ", right=" + right + '}';
        }
    }

    // 合并区间方法
    public static List<Index> mergeIntervals(List<Index> indices) {
        // 如果集合为空或只有一个元素，直接返回
        if (indices == null || indices.size() <= 1) {
            return indices;
        }

        // 存放合并后的结果
        List<Index> merged = new ArrayList<>();

        // 按 left 排序
        indices.sort((a, b) -> Integer.compare(a.left, b.left));

        // 初始区间
        Index current = indices.get(0);
        for (int i = 1; i < indices.size(); i++) {
            Index next = indices.get(i);

            // 如果当前区间的右端点大于或等于下一个区间的左端点，合并
            if (current.right >= next.left) {
                // 合并区间，更新右端点为最大值
                current.right = Math.max(current.right, next.right);
            } else {
                // 如果没有重叠，当前区间加入结果，更新当前区间为下一个区间
                merged.add(current);
                current = next;
            }
        }
        // 将最后一个区间添加到结果中
        merged.add(current);

        return merged;
    }

    // 测试方法
    public static void main(String[] args) {
        List<Index> indices = new ArrayList<>();
        indices.add(new Index(1, 3));
        indices.add(new Index(2, 6));
        indices.add(new Index(8, 10));
        indices.add(new Index(15, 18));
        indices.add(new Index(4, 5));

        System.out.println("原始区间: " + indices);

        List<Index> merged = mergeIntervals(indices);
        System.out.println("合并后的区间: " + merged);
    }
}
